package com.example.demo.Calss18_dongtaiguihua;

/**
 * @program: java_base
 * @description: class21_每张相同面值的货币不同，组成相同的值问题
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/04 15:34
 * arr[] 货币数组，给定目标金额aim>0
 * 面值相同也 视为不同，因为有钱的唯一编号
 * 返回组合数：arr[] 有多少种组合数，==aim值
 */
public class Code02_CoinsWayEveryPaperDifferentDemo {

    public static int coinWays(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }


    // 有多少中方式 取得 值为rest
    private static int process(int[] arr, int index, int rest) {
        // 已经凑成了
        if (rest < 0) {
            return 0;
        }
        if (index == arr.length) { // 没钱了！钱序列没钱了
            return rest == 0 ? 1 : 0;
        }
        return process(arr, index + 1, rest)
                + process(arr, index + 1, rest - arr[index]);
    }


}
